package day_2022_12_to_3.year2023;
import java.util.*;
/**
 * @author haomin
 * @date 2023/01/04 22:24
 **/
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Day1_4_Review {
    class Solution {
        // 方法一：Set集合
        public int findRepeatNumber1(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for(int i : nums) {
                if(!set.add(i)) return i;
            }
            return -1;
        }

        // 方法二：排序
        public int findRepeatNumber2(int[] nums) {
            Arrays.sort(nums);
            for(int i = 1; i < nums.length; ++i) {
                if(nums[i] == nums[i-1]) return nums[i];
            }
            return -1;
        }

        // 方法三： 元素归位
        public int findRepeatNumber(int[] nums) {
            int i = 0;
            while(true) {
                int m = nums[i];
                int n = nums[m];
                if(m == i) i++;
                else if(m == n) return m;
                else {
                    nums[m] = m;
                    nums[i] = n;
                }
            }
        }
    }

    class Solution2 {
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            if(matrix.length == 0 || matrix[0].length == 0) return false;
            int m = matrix.length, n = matrix[0].length;
            int row = 0, col = n-1;
            while(row < m && col >= 0) {
                if(matrix[row][col] > target) col--;
                else if(matrix[row][col] < target) row++;
                else return true;
            }
            return false;
        }
    }


    class Solution3 {
        public String replaceSpace(String s) {
            if(s.length() == 0) return s;
            StringBuffer sb = new StringBuffer();
            for(int i = 0; i < s.length(); ++i) {
                char c = s.charAt(i);
                if(c == ' ') sb.append("%20");
                else sb.append(c);
            }
            return sb.toString();
        }
    }

    class Solution4 {
        public int[] reversePrint(ListNode head) {
            if(head == null) return new int[0];
            Deque<Integer> s = new LinkedList<>();
            while(head != null) {
                s.push(head.val);
                head = head.next;
            }
            return s.stream().mapToInt(Integer::intValue).toArray();
        }
    }
}